package com.springboot.shanhexin.unit;

import java.io.IOException;
/*
* 		GreedAlo ts = new GreedAlo(5);//景点数目
		int[] a={1,1,2,3,4};          //景点横纵坐标
		int[] b={2,1,1,1,1};
		String[] spot= {"a","b","c","d","e"};//景点数组
		ts.init(a,b);
		spot=ts.solve(spot);//输出的景点数组
* */

public class GreedAlo {

    public int cityNum; // 城市数量
    public int[][] distance; // 距离矩阵

    public int[] colable;//代表列，也表示是否走过，走过置0
    public int[] row;//代表行，选过置0

    public GreedAlo(int n) {
        cityNum = n;
    }

    //初始化
    public void init(int[][] distances) throws IOException {
        // 距离矩阵赋值
        distance = new int[cityNum][cityNum];
        for (int i = 0; i <distances.length ; i++) {
            for (int j = 0;j<distances.length;j++){
                distance[i][j]=distances[i][j];
            }
        }
        colable = new int[cityNum];
        colable[0] = 0;
        for (int i = 1; i < cityNum; i++) {
            colable[i] = 1;
        }

        row = new int[cityNum];
        for (int i = 0; i < cityNum; i++) {
            row[i] = 1;
        }
    }

    public String[] solve(String[] spot){ //拿到规划好的景点名

        int[] temp = new int[cityNum];
        String[] spot_temp=new String[cityNum];//调换景点次序
        for (int i = 0; i < spot.length; i++) {
            spot_temp[i]=spot[i];
        }

        //int s=0;//距离
        int i=0;//当前节点
        int j=0;//下一个节点
        int m=1;//景点次序
        //默认从0开始
        while(row[i]==1){
            //复制一行
            for (int k = 0; k < cityNum; k++) {
                temp[k] = distance[i][k];
                //System.out.print(temp[k]+" ");
            }
            //System.out.println();
            //选择下一个节点，要求不是已经走过，并且与i不同
            j = selectmin(temp);
            //找出下一节点
            row[i] = 0;//行置0，表示已经选过
            colable[j] = 0;//列0，表示已经走过

            if (j!=0) {
                spot[m]=spot_temp[j];
                m=m+1;
            }
            //System.out.println(i + "-->" + j);
            //System.out.println(distance[i][j]);
            //s = s + distance[i][j];计算距离
            i = j;//当前节点指向下一节点
        }
        return spot;

    }

    public int selectmin(int[] p){
        int j = 0, m = p[0], k = 0;
        //寻找第一个可用节点，注意最后一次寻找，没有可用节点
        while (colable[j] == 0) {
            j++;
            //System.out.print(j+" ");
            if(j>=cityNum){
                //没有可用节点，说明已结束，最后一次为 *-->0
                m = p[0];
                break;
                //或者直接return 0;
            }
            else{
                m = p[j];
            }
        }
        //从可用节点J开始往后扫描，找出距离最小节点
        for (; j < cityNum; j++) {
            if (colable[j] == 1) {
                if (m >= p[j]) {
                    m = p[j];
                    k = j;
                }
            }
        }
        return k;
    }


    public void printinit() {
        System.out.println("print begin....");
        for (int i = 0; i < cityNum; i++) {
            for (int j = 0; j < cityNum; j++) {
                System.out.print(distance[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println("print end....");
    }
}


